分析演算法

分析演算法，即是分析一個演算法的效率，來決定我們要使用哪一種演算法，而效率的分析方式通常會使用時間進行分析，忽略記憶體，或是頻寬之類的議題。

在分析一個演算法時，我們通常會使用兩種工具，一種是使用模型進行分析，另一種是數學方法，模型的部分，需要能夠描述演算法使用的資源或是付出的代價，我們這裡使用隨機存取機(random-access machine, RAM)作為描述演算法所使用的資源或時間複雜度的模型，隨機存取機常常應用在計算複雜性理論(Computational complexity theory)中。

圖靈機（Turing Machine，TM）

圖靈機（Turing Machine，TM），又被稱為確定型圖靈機。是一種抽象的數學計算模型。可以看作等價於任何有限次數數學邏輯運算過程的邏輯機器。

基本上。圖靈機就是模擬人們使用紙筆計算數學問題的過程，而這樣的過程我們可以定義為以下兩個步驟

1. 在紙上寫上或是擦掉一個記號
2. 把注意力從紙的一個位置移動到另一個位置

為了類比人類的運算過程，圖靈建造出一種假想機器，由以下部分所組成

1. Tape : 表示一條一條無限長的紙帶，劃分出一格一格的小格子，每一個格子包含一個有限字母表的符號。
2. Head : 表示讀寫頭，讀寫頭可以在膠帶上向左或是向右移動，能夠讀取當前格子的符號，或是改變當前格子的符號。
3. Table : 一套控制讀寫的規則，根據機器目前所處的狀態以及讀寫頭所讀取到格子的內容來決定執行什麼樣的動作，並改變暫存器的值，令機器進入新的狀態，按照以下幾個順序告知圖靈機
   1. 寫入或是擦掉目前的符號
   2. 移動Head， 'L'向左， 'R'向右或者'N'不移動
   3. 保持目前的狀態或是移動到下一個狀態
4. 一個狀態暫存器 : 儲存圖靈機目前的狀態。圖靈機的狀態數目是有限的，並且含有一個特殊的狀態，稱為停機狀態。
5. 狀態轉移方程式(Transition Function) : 舉例: 表示如果目前狀態為q,格子內的內容為字符c，則將目前格子的字符改成d，讀寫頭轉向左側/右側/停止，進入p狀態，一但轉入特定狀態h，則停機。

舉一個簡單運用圖靈機的例子
Example 1. 把紙帶上儲存的值加1

定義演算法:

1. 初始狀態 : head指向最右邊內容為'#'的儲存格
2. head的移動與動作 : 如果指到的儲存格內容為1，則將1變為0，並head向左移動。如果指到的儲存格內容為0，則將0變為1，並head向右移動
3. 當head向右移動時不改變儲存格上面的數值
4. 最終狀態 : head向右移動，知道head指向'#'的單元格結束

狀態表格 :

狀態表達式 :
(1, 0, L)，如果Head碰到1，會將內容改成0，並Head向左移動
(#, 1, R)，如果Head碰到#，會將內容改成1，並Head向右移動
(0, 0, R)，如果Head碰到0，會將內容改成0，並Head往右移動
(#, #, N)，如果Head碰到#，會將內容改成#，並Head停止

隨機存取機(random-access machine RAM)

在計算複雜性理論內，隨機存取圖靈機(random-access Turing machines)是一種變形的圖靈機，可以想像成它是一個巨大的陣列，用來處理大小較小的複雜度演算法，特別是使用O的複雜度演算法.在隨機存取圖靈機上，多了一個特殊的指針磁帶(儲存格的概念)，大小是對數空間，字母是二進位單字(0和1)。圖靈機有一個特殊的狀態(state)，當指到這個狀態而指針磁帶的數字(二進位)是’p’時，圖靈機會將工作磁帶上面的指針移動到輸入的第p個符號。

這特性讓圖靈機可以直接讀取輸入的特定字母，而不需要花時間去處理整條輸入。這對使用少於線性時間的複雜度演算法來說，是必要的(因爲處理整個輸入的時間是線性時間)^2

隨機存取機和圖靈機在計算能力上是等價的，但是在計算速度上有所不同

插入排序法分析(Insertion sort)

插入排序法所需花費的時間會根據輸入資料的長度而增加，且根據輸入集合已經被排序的程度，插入排序法可能需要花費不同的時間來排序兩個相同長度的輸入集合。一般來說，演算法所需要的時間與輸入集合元素的多寡成正比，我們使用一種函數去描述一個演算法所需要的時間，因此，我們需要先定義所謂的運行時間和輸入的規模。

輸入的規模，根據我們研究的問題而有不同的定義，如在排序問題或是離散傅立葉轉換，輸入的規模會根據輸入集合的元素個素，例如 : 有一個含有10個元素的陣列需要排列。對於其他問題，如兩個數字的相乘，輸入規模可能運用二進位的方式來表示輸入需要的總位數。對於每一個問題，我們需要定義輸入規模的量級。

一個演算法在特定輸入所需花費的時間是指執行操作的步數或是操作數。我們使用這樣的觀點，來觀察插入排序法的虛擬碼，去評估這個演算法所需要花費的時間，假定第i行指令每一次執行時間為ci(雖然每一行可能需要不同的數量與時間)，ci為一個常數。這個觀點是基於RAM模型的。

在下面的討論中，我們由簡單到複雜，由ci到具體的步數，寫出插入排序法所需時間的表示式。

這個演算法所需要花費的時間即為times的加總。需要執行步且執行n次的一條述句需要的時間，以下為假設輸入有n個元素的陣列插入排序法所需要的時間

即使我們給定的輸入元素數量皆相同，演算法也可能因為輸入陣列的排序情況而有不同的執行時間，例如在插入排序中，如果輸入的陣列已經完成排序，則會出現最佳情況，我們可以發現在第5行程式碼，，不會進入while迴圈，我們可以計算出在這樣的最佳情況下的運行時間

我們可以把簡化為，簡化成，把表示成，其中和根據所決定。因此，我們可以把表示成n的線性函數。

最糟的情況為整個陣列進行反向排序，我們必須將陣列中每一個元素和已經排序的子陣列中每一個元素進行比較，對，，在第5行的while

將以代入，得到以下

第6行和第7行也是如此，整理過後，得到整個運行時間

把有關於的部分用a, b, c取代過後，得到，a, b, c取決於，得到這是一個n的二次函數。

整理一下，我們得到

• 最佳情況 :
• 最壞情況 :

最壞情況與平均情況分析

對於一個演算法，我們通常只在意他的最壞情況，也就是對於長度為n的輸入，演算法運行的最長時間。而這樣的想法是基於以下三個理由

• 只要我們知道一個演算法運行時間的上界，我們就可以不必對運行時間做出各種複雜的猜測並可以預期這個演算法的不會超過這個時間。
• 對於某一些演算法來說，最壞情況是頻繁出現的。
• 演算法的平均情況時常和他的最壞情況一樣的糟糕，平均情況的運行時間和最壞情況往往是相同的，以插入排序法為例，平均情況得出來的時間規模也同樣是n的二次函數。

增加量級概念

我們在上面用了一些抽象的方法使我們分析插入排序法更加的方便，把最壞的情況表示成，我們可以想像，當n無限的放大，可以發現對於整體二次函數的影響更大，也因此在分析演算法時，我們常常只在意演算法時間規模的最高次數項，直接將 當作 看待。我們大致上會將這樣的表示法以Θ表示，後面我們會對這個符號進行精確的定義。

資料來源:Introduction to algorithms 3rd, 圖片來自網路